Quá trình quyết định Markov là một trò chơi ngẫu nhiên với người chơi duy nhất.

Có thể tuân theo từng phần

Lời giải ở trên giả thiết rằng trạng thái s {\displaystyle s}  đã biết khi hành động được thực hiện; nếu không thì  π ( s ) {\displaystyle \pi (s)}  không thể được tính toán. Khi giả thiết này không đúng, bài toán được gọi là một quá trình quyết định Markov có thể tuân theo từng phần hoặc POMDP.

Một cải tiến chính trong lĩnh vực này đã được thực hiện bởi Burnetas và Katehakis trong "Optimal adaptive policies for Markov decision processes" (các nguyên tắc thích nghi tối ưu cho các quá trình quyết định Markov).[2] Trong công trình này một lớp các nguyên tắc thích nghi sở hữu các thuộc tính tốc độ hội tụ cực đại đều cho  tổng phần thưởng đường chân trời hữu hạn dự kiến, được xây dựng theo các giả định về các không gian trạng thái-hành động và sự tối giản của luật chuyển tiếp. Các nguyên tắc này quy định rằng sự lựa chọn của các hành động, tại mỗi trạng thái và khoảng thời gian, phải dựa vào các chỉ số là các lạm phát của bên phải của các phương trình tối ưu phần thưởng trung bình được ước lượng.

Học tăng cường

Nếu xác suất hoặc phần thưởng là chưa biết, bài toán là bài toán học tăng cường (Sutton và Barto, 1998).

Để thực hiện mục đích này, việc định nghĩa một hàm thúc đẩy là rất cần thiết, tương ứng với việc thực hiện hành động a {\displaystyle a} và sau đó tiếp tục tối ưu hóa (hoặc theo bất kỳ nguyên tắc nào mà ta đang có):

  Q ( s , a ) = ∑ s ′ P a ( s , s ′ ) ( R a ( s , s ′ ) + γ V ( s ′ ) ) .   {\displaystyle \ Q(s,a)=\sum _{s'}P_{a}(s,s')(R_{a}(s,s')+\gamma V(s')).\ }

Trong khi hàm này cũng chưa biét, kinh nghiệm trong quá trình học sẽ được dựa trên các cặp ( s , a ) {\displaystyle (s,a)} (cùng với kết quả s ′ {\displaystyle s'} ); đó là, "Tôi đã ở trong trạng thái s {\displaystyle s} và tôi cố gắng thực hiện a {\displaystyle a} và s ′ {\displaystyle s'} xảy ra"). Vì vậy, ta có một dãy Q {\displaystyle Q} và sử dụng kinh nghiệm để cập nhật nó trực tiếp. Điều này còn được gọi là Q‑learning.

Học tăng cường có thể giải quyết các quá trình quyết định Markov mà không cần đặc điểm rõ ràng của các xác suất chuyển đổi;Các giá trị của các xác suất chuyển tiếp là cần thiết trong phép lặp giá trị và nguyên tắc.Trong tăng cường việc học, thay vì các đặc điểm rõ ràng của các xác suất chuyển tiếp, các xác suất chuyển tiếp được xử lý thông qua một trình mô phỏng thường khởi động lại nhiều lần từ một trạng thái ngẫu nhiên đầu tiên thống nhất. Học tăng cường cũng có thể được kết hợp với xấp xỉ hàm để giải các bài toán có số lượng trạng thái rất lớn.

Giải thích phân loại lý thuyết

Ngoại trừ các phần thưởng, một quá trình quyết định Markov ( S , A , P ) {\displaystyle (S,A,P)} có thể được hiểu trong khuôn khổ của Lý thuyết Phân loại. Cụ thể. cho A {\displaystyle {\mathcal {A}}} là ký hiệu của  free monoid với tập con A. Cho Dist là ký hiệu của Kleisli category của Giry monad. Thì một hàm tử A → D i s t {\displaystyle {\mathcal {A}}\to \mathbf {Dist} } mã hóa cả tập S của các trạng thái và cả hàm xác suất P.

Bằng cách này, các quá trình quyết định Markov có thể được tổng quát hóa từ các monoid (các phân loại với một đối tượng) với các thể loại tùy ý. Ta có thể gọi kết quả ( C , F : C → D i s t {\displaystyle ({\mathcal {C}},F:{\mathcal {C}}\to \mathbf {Dist} } một quyết định Markov phụ thuộc-ngữ cảnh, bởi vì di chuyển từ một đối tượng sang một đối tượng khác trong C {\displaystyle {\mathcal {C}}} thay đổi tập các hành động khả dụng và tập các trạng thái có khả năng xảy ra.